def is_repeating_subseq(subseq):
    """检查子序列是否可以被分解为更小的重复单元"""
    n = len(subseq)
    for i in range(1, n//2 + 1):
        if n % i == 0 and subseq == subseq[:i] * (n // i):
            return True
    return False

def mark_repeating_sequences(seq):
    n = len(seq)
    if n == 0:
        return []
    
    # 找到最长的有效重复子序列（不能被分解为更小的重复单元）
    max_total_len = 0  # 子序列长度 * 重复次数
    best_subseq_len = 0
    best_start = 0
    best_repeats = 1
    
    # 从最长可能的子序列开始尝试，找到就可以提前退出
    for subseq_len in range(n//2, 0, -1):
        # 检查所有可能的起始位置
        for start in range(n - 2 * subseq_len + 1):
            subseq = seq[start:start+subseq_len]
            
            # 检查子序列是否可以被分解为更小的重复单元
            if is_repeating_subseq(subseq):
                continue
            
            repeats = 1
            current_pos = start + subseq_len
            
            # 计算这个子序列重复了多少次
            while current_pos + subseq_len <= n and seq[current_pos:current_pos+subseq_len] == subseq:
                repeats += 1
                current_pos += subseq_len
            
            # 更新最长有效重复子序列
            total_len = subseq_len * repeats
            if repeats > 1 and total_len > max_total_len:
                max_total_len = total_len
                best_subseq_len = subseq_len
                best_start = start
                best_repeats = repeats
        
        # 如果已经找到一个较长的有效重复子序列，可以提前退出
        if max_total_len > 0:
            break
    
    # 如果没有找到有效重复子序列，全部标记为0
    if best_repeats <= 1:
        return [0] * n
    
    # 确定前缀、重复序列和结尾序列的范围
    repeat_end = best_start + best_subseq_len * best_repeats
    
    # 创建标记列表
    marks = []
    
    # 标记前缀
    for i in range(best_start):
        marks.append(0)
    
    # 标记重复序列
    for r in range(best_repeats):
        for i in range(best_subseq_len):
            marks.append(r + 1)
    
    # 标记结尾
    for i in range(repeat_end, n):
        marks.append(0)
    
    return marks

def find_all_indices(lst, target):
    # 列表推导式，遍历列表并记录符合条件的索引
    return [index for index, value in enumerate(lst) if value == target]


if __name__ == "__main__":
    # 测试代码
    test_list2 = [
        '1', '2', '3', '4',
        '5', '5', '5', '6','7'
    ]  

    print("输入列表2长度:", len(test_list2))
    result = mark_repeating_sequences(test_list2)
    print("标记结果2:", result)

    # 验证结果
    print("\n标记分布:")
    from collections import Counter
    print(Counter(result))

    # 测试
    my_list = [1, 2, 2, 2, 3, 3]
    result = find_all_indices(my_list, 2)
    print(result)  # 输出: [1, 2, 3]